import java.util.ArrayList;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-09-25
 * Time:7:51
 */

class Solution02 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search (int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * BM18 二维数组中的查找
     * @param target
     * @param array
     * @return
     */
    public boolean Find1(int target, int [][] array) {
        if (array == null || array.length == 0) return false;
        int row = array.length;// 行数
        int col = array[0].length;// 列数
        int n = row - 1;
        int m = 0;
        while (n >= 0 && m < col) {
            if (array[n][m] == target) {
                return true;
            }
            else if (array[n][m] < target) {
                m++;
            }
            else {
                n--;
            }
        }
        return false;
    }

    public boolean Find(int target, int [][] array) {
        if (array == null || array.length == 0) return false;
        int row = array.length;// 行数
        int col = array[0].length;// 列数
        int n = row >> 1;
        int m = col >> 1;
        while (n >= 0 && n < col && m >= 0 && m < col) {
            if (array[n][m] == target) {
                return true;
            }
            else if (array[n][m] < target) {
                m++;
            }
            else {
                n--;
            }
        }
        return false;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 寻找峰值
     * 假设num[-1] = nums[n] = -无穷 (说明题目中一定存在峰值)
     * num[i] != num[i+1]
     * @param nums int整型一维数组
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }

    /**
     * 数组中的逆序对
     * @param array
     * @return
     */
    public int InversePairs(int [] array) {
        // 分治需要使用递归，因此重新封装到一个方法中
        return merge(array, 0, array.length - 1);
    }

    private int merge(int[] array, int start, int end) {
        // 分到最小（数组中只有一个元素）此时逆序数为0
        if (start >= end) return 0;
        int count = 0;//用于记录逆序数 逆序数=两个带合并数组本身的逆序数+两个数组之间的逆序数
        int mid = (start + end) >> 1;//找到分割点（数组中点）
        count += merge(array, start, mid);//左边部分，递归分割
        count += merge(array, mid + 1, end);//右边部分

        // 归并排序
        int[] tmp = new int[end - start + 1];//使用一个临时数组，存放排序后的元素
        int l = start;//指向待合并的第一个数组首元素
        int r = mid + 1;//指向待合并的第二个数组首元素
        int i = 0;//指向临时数组
        while (l <= mid && r <= end) {
            if (array[l] < array[r]) {//升序，直接复制
                tmp[i] = array[l];
                i++;
                l++;
            } else {//后面数组中的数小于前面数组中的数->逆序，记录逆序数+1
                count = (count + (mid + 1 - l)) % 1000000007;
                tmp[i] = array[r];
                r++;
                i++;
            }
        }
        //多余的元素复制到临时数组中
        while (l <= mid) {
            tmp[i++] = array[l++];
        }
        while (r <= end) {
            tmp[i++] = array[r++];
        }
        //将临时数组复制给array
        for (int j = 0; j < i; j++) {
            array[j + start] = tmp[j];
        }
        return count;
    }

    /**
     * 旋转数组的最小数字
     * @param array
     * @return
     */
    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (array[mid] > array[right]) {
                // 最小数在右边
                left = mid + 1;
            } else if (array[mid] < array[right]) {
                // 最小数在左边，包括mid
                right = mid;
            } else {
                right--;
            }
        }
        return array[left];
    }

    // 题目的案例是以ArrayList的形式输入的
    public int minNumberInRotateArray2(ArrayList<Integer> array) {
        int left = 0;
        Integer[] arr = array.toArray(new Integer[0]);
        int right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] > arr[right]) {
                // 最小数在右边
                left = mid + 1;
            } else if (arr[mid] < arr[right]) {
                // 最小数在左边，包括mid
                right = mid;
            } else {
                right--;
            }
        }
        return arr[left];
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串
     * @param version2 string字符串
     * @return int整型
     */
    public int compare (String version1, String version2) {
        int len1 = version1.length();
        int len2 = version2.length();
        int i = 0;
        int j = 0;
        while (i < len1 || j < len2) {
            // 截取version1的数字
            int num1 = 0;
            while (i < len1 && version1.charAt(i) != '.') {
                num1 = num1 * 10 + (version1.charAt(i) - '0');
                i++;
            }
            i++;
            // 截取version2的数字
            int num2 = 0;
            while (j < len2 && version2.charAt(j) != '.') {
                num2 = num2 * 10 + (version2.charAt(j) - '0');
                j++;
            }
            j++;
            if (num1 > num2) return 1;
            if (num1 < num2) return -1;
        }
        return 0;
    }

}

public class Test02 {
    public static void main(String[] args) {
        Solution02 s = new Solution02();
        int[] a = {3, 100, 200, 3};
        System.out.println(s.minNumberInRotateArray(a));
    }
}
